package com.markus.code.二叉树.study;

import com.markus.basic.Java基础.重写与重载.B;

/**
 * Author:markusZhang
 * Date:Create in 2020/9/3 14:44
 * todo:
 */
public class ByteDance {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
    public boolean isPathSum(TreeNode root,int sum){
        if (root == null){
            return false;
        }
        return process(root,0,sum);
    }
    private boolean process(TreeNode x,int cur,int sum){
        if (x == null){
            return false;
        }
        cur += x.val;
        if (cur == sum){
            return x.left==null && x.right==null;
        }
        return process(x.left,cur,sum) || process(x.right,cur,sum);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.right.right = new TreeNode(9);
        root.right.right.right = new TreeNode(1);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(11);
        root.left.right.left = new TreeNode(2);
        //加个反例
        root.left.right.left.left = new TreeNode(1);
        root.left.right.right = new TreeNode(7);
        ByteDance demo = new ByteDance();
        System.out.println(demo.isPathSum(root,22));
    }
}
